package leetcode_1001_1100;

public class LeeCode_1031 {
    public static void main(String[] args) {
        System.out.println(maxSumTwoNoOverlap(new int[]{0, 6, 5, 2, 2, 5, 1, 9, 4}, 1, 2));
        System.out.println(maxSumTwoNoOverlap(new int[]{3,8,1,3,2,1,8,9,0}, 3, 2));
    }
    private static int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int[] dpF = getDp(sums, firstLen);
        int[] dpS = getDp(sums, secondLen);
        int ans = 0;
        int i = firstLen + secondLen - 1;
        while (i < n){
            ans  = Math.max(sums[i + 1] - sums[i + 1 - secondLen] + dpF[i - secondLen],
                    Math.max(sums[i + 1] - sums[i + 1 - firstLen] + dpS[i - firstLen], ans));
            i++;
        }
        return ans;
    }
    private static int[] getDp(int[] sums, int len){
        int l = 0, r = len - 1;
        int[] firs = new int[sums.length - 1];
        firs[r] = sums[r + 1] - sums[l];
        int max = firs[r];
        while (r < sums.length - 1){
            int sum = sums[r + 1] - sums[l];
            if (sum > max){
                max = sum;
            }
            firs[r] = max;
            l++;
            r++;
        }
        return firs;
    }
}
